『计算机的组成与设计』-指令：计算机的语言

当你的噩梦里再也没有恶龙和沼泽，而全都是生活难题的那一刻，你就知道你长大了。

计算机语言中的基本单词称为指令。一台计算机的全部指令称为该计算机的指令集。
尽管机器语言种类繁多，但他们之间十分相似，其差异性更像人类语言的”方言”。
本篇讲解 MIPS 指令集。

Intel x86，在 PC 以及后 PC 时代的云计算领域占统治地位
ARMv8 将 ARMv7 的地址范围从 32 位扩展到 64 位。讽刺的是，ARMv8 更接近 MIPS 而非 ARMv7

注意: MIPS 和 RAM 属于精简指令集(Reduced Instruction Set Computer，RISC)，而 x86 属于复杂指令集(Complex Instruction Set Computer，CISC)。
现在在 RISC 占统治地位的是 RAM，在 CISC 占统治地位的是 x86。MIPS 已死，MIPS 永生。
以 MIPS 为代表的精简指令集关注的是:

减少指令的类型
降低指令复杂度

基本原则: a simple CPU is a faster CPU。

MIPS 操作数

名字	示例	注释
32 个寄存器	$s0-$s7,$t0-$t9,$zero,$a0-$a3, $v0-$v1,$k0-$k1,$gp,$fp,$sp, $ra,$at	寄存器用于数据的快速存取，在 MIPS 中，只能对放在寄存器中的数据执行算术操作，寄存器 $zero 恒为 0，$at 被汇编器保留，处理大常数。
2³² 个存储器字	Memory[0],Memory[4],…, Memory[4294967292]	存储器只能通过数据传输指令访问。MIPS 使用字节编址，所以连续字地址相差 4

MIPS 寄存器字解释

编号	名称	用途
0	$zero	The Constant Value 0
1	$at	Assembler Temporary
2-3	$v0-$v1	Values of Function Results and Expression Evaluation
4-7	$a0-$a3	Arguments
8-15	$t0-$t7	Temporaries
16-23	$s0-$s7	Saved Temporaries
24-25	$t8-$t9	Temporaries
26-27	$k0-$k1	Reserved of OS Kernel
28	$gp	Global Pointer
29	$sp	Stack Pointer
30	$fp	Frame Pointer
31	$ra	Return Address

MIPS 指令

算术指令

指令	示例	含义	注释
加法	add $s1, $s2, $s3	$s1 = $s2 + $s3	三个寄存器操作数
减法	sub $s1, $s2, $s3	$s1 = $s2 - $s3	三个寄存器操作数
立即数加法	addi $s1, $s2, 20	$s1 = $s2 + 20	用于加常数数据

数据传输指令

指令	示例	含义	注释
取字	lw $s1, 20($s2)	$s1 = Memory[$s2 + 20]	将一个字从内存中取到寄存器
存字	sw $s1, 20($s2)	Memory[$s2 + 20] = $s1	将一个字从寄存器中存到内存
取半字	lh $s1, 20($s2)	$s1 = Memory[$s2 + 20]	将半个字从内存中取到寄存器
存半字	sw $s1, 20($s2)	Memory[$s2 + 20] = $s1	将半个字从寄存器中存到内存
取无符号半字	lhu $s1, 20($s2)	$s1 = Memory[$s2 + 20]	将半个字从内存中取到寄存器
取字节	lb $s1, 20($s2)	$s1 = Memory[$s2 + 20]	将一个字节从内存中取到寄存器
存字节	sb $s1, 20($s2)	Memory[$s2 + 20] = $s1	将一个字节从寄存器中存到内存
取无符号字节	lbu $s1, 20($s2)	$s1 = Memory[$s2 + 20]	将一个字节从内存中取到寄存器
取链接字	ll $s1, 20($s2)	$s1 = Memory[$s2 + 20]	取字作为原子交换的前半部分
存条件字	sc $s1, 20($s2)	Memory[$s2 + 20] = $s1; $s1 = 0 or 1	存字作为原子交换的后半部分
取立即数高位	lui $s1, 20	$s1 = 20 * 2¹⁶	取立即数并放在高16位

位操作

指令	示例	含义	注释
与	and $s1,$s2,$s3	$s1 = $s2 & $s3	三个寄存器操作数按位与
或	or $s1,$s2,$s3	$s1 = $s2 \| $s3	三个寄存器操作数按位或
或非	nor $s1,$s2,$s3	$s1 = ~($s2 \| $s3)	三个寄存器操作数按位或非
立即数与	andi $s1,$s2,20	$s1 = $s2 & 20	和常数按位与
立即数或	ori $s1,$s2,20	$s1 = $s2 \| 20	和常数按位或
逻辑左移	sll $s1,$s2,10	$s1 = $s2 << 10	根据常数左移相应位
逻辑右移	srl $s1,$s2,10	$s1 = $s2 >> 10	根据常数右移相应位

条件分支

指令	示例	含义	注释
相等时跳转	beq $s1,$s2,25	if($s1 == $s2) go to PC + 4 + 100	相等检测，和 PC 相关的跳转
不相等时跳转	bne $s1,$s2,25	if($s1 != $s2) go to PC + 4 + 100	不相等检测，和 PC 相关的跳转
小于时置位	slt $s1,$s2,$s3	if($s2 < $s3) $s1 = 1; else $s1 = 0	比较是否小于
无符号数比较小于时置位	sltu $s1,$s2,$s3	if($s2 < $s3) $s1 = 1; else $s1 = 0	比较是否小于无符号数
无符号数比较小于立即数时置位	slti $s1,$s2,20	if($s2 < 20) $s1 = 1; else $s1 = 0	比较是否小于常数
无符号数比较小于无符号立即数时置位	sltiu $s1,$s2,20	if($s2 < 20) $s1 = 1; else $s1 = 0	比较是否小于无符号常数

无条件跳转

指令	示例	含义	注释
跳转	j 2500	goto 10000	跳转到目标地址
跳转至寄存器所指地址	jr $ra	go to $ra	用于 switch 语句以及过程调用
跳转并链接	jal 2500	$ra = PC + 4; go to 10000	用于过程调用

MIPS 指令的特点

固定的指令长度(32-bit 即1 word)
简化了从存储器取指令。
简单的寻址模式
简化了从存储器取操作数。
指令数量少，功能简单
简化指令的执行过程。
只有 load 和 store 指令能访问存储器

硬件设计三原则:

任何计算机必须能执行算术运算。 MIPS 汇编语言使用 add a, b, c 表示将 b 和 c 相加的结果赋值给 a。
与加法类似的指令一般都有三个操作数: 两个进行运算的数和一个保存结果的数。
这种情况说明了硬件设计的三条基本原则的第一条:
设计原则1: 简单源于规整。
MIPS 算术运算指令的操作数有严格限制。他们必须来自寄存器。MIPS 体系结构中寄存器的大小为 32 个，因此在 MIPS 体系结构中将其称为字 word。
高级语言中的变量与寄存器的一个主要区别就是寄存器的数量有限。
寄存器个数限制为 32 个的理由可表示为硬件设计的三条基本原则的第二条:

设计原则2: 越小越快。
大量的寄存器可能会使时钟周期变长，因为电信号传输更远的距离必然花费更多时间。

设计原则3: 优秀的设计需要折中的方案
MIPS 设计者为保持所有指令长度相同，采用了一种折中方案: 不同类型的指令采用不同的指令格式。

在高级语言中，有保存仅含一个数据的简单变量。也有像数组或结构那样的复杂数据结构。处理器只将少量数据保存在寄存器中，数据结构是存放在存储器中的。
并且之前说过，MIPS 的算术运算只能对寄存器进行操作，因此，MIPS 必须包含在存储器和寄存器之间传送数据的指令。这些指令称为数据传送指令。
为了访问存储器中的一个字，指令必须给出存储器地址(address)。
将数据从储存器复制到寄存器的数据传输指令称为取数(load)指令。取数指令的格式是操作码之后接着目标寄存器，在后面是用来访问存储器的常数和寄存器。常数和第二个寄存器中的值相加即得到存储器地址。取数指令助记符为 lw(load word)。
数据传输指令的常数称为偏移量(offset)，存放基址的寄存器称为基址寄存器(base register)。
与取数对应的指令称为存数 store word。
有一个常数操作数的快速加法指令称为加立即数(add immediate，addi)。MIPS 支持负常数，因此不需要设置减立即数指令。

示例:

假设

A 是一个 100 个字的数组，首地址在寄存器 $19 中
变量 h 对应寄存器 $18
临时数据存储在寄存器 $8

那么
A[10] = h + A[3]对应的 MIPS 指令是:

lw $8, 12($19)
add $8, $18, $8
sw $8, 40($19)

MIPS 指令的基本格式

指令的布局形式叫做指令格式。

注意:

在 R 型指令中，rd 表示用于存放结果的目的操作数，rs 表示第一个源操作数，rt 表示第二个源操作数
在 I 型指令中，rt 表示接收取数结果的目的操作数，rs 表示源操作数

R 型指令示例

如: lw rd, rs, rt

add $8, $9, $10

查指令编码表可得:
opcode: 0, funct 32, shamt: 0(非移位指令)
根据操作数可得:
rd = 8(目的操作数), rs = 9(第一个源操作数), rt = 10(第二个源操作数)
所以 R 指令为:
000000 01001 01010 01000 00000 100000

sll $t2, $s0, 4

查指令编码表可得:
opcode: 0, funct 0, shamt(shift amount): 4
根据操作数可得:
rd = 10(目的操作数), rs = 0(第一个源操作数), rt = 16(第二个源操作数)
所以 R 指令为:
000000 00000 10000 01010 00100 000000

I 型指令示例

如: addi rt, imm(rs)

addi $21, $22, -50

查指令编码表可得:
opcode: 8
分析指令可得:
rs = 22, rt = 21, imm = -50
所以 I 指令为:
001000 10110 10101 1111111111001110

决策指令

程序语言通常使用if语句描述决策，有时也使用 go to 语句和标签。
MIPS 汇编语言中有两条类似 if 和 go to 语句功能的指令:

beq reg1, reg2, L1
该指令表示: 如果 reg1 与 reg2 中的数值相等，则跳转标签为 L1 的语句执行。

beq(branch if equal)表示如果相等则分支。
2. bne reg1, reg2, L1
该指令表示: 如果 reg1 与 reg2 中的数值不相等，则跳转标签为 L1 的语句执行。
bne(branch if not equal)表示如果不相等则分支。

这两条指令称为条件分支指令 conditional branch。指该指令先比较两个值，根据比较的结果决定是否从程序中的一个新地址开始执行指令序列。

还有另一种分支指令，称为无条件分支指令 unconditional branch。当遇到这种指令，程序必须分支。MIPS 将该指令命名为 j 意为 jump。

循环

无论是 if 语句，还是循环语句，决策起着重要作用，这两种情况，决策的汇编指令是相同的。

while (save[i] == k)
i += 1;

假设 i 和 k 保存在$s3和$s5中，save 数组基址为$s6，将上述代码转为 MIPS 汇编。

Loop: sll $t0, $s3, 2
add $t0, $t0, $s6
bne $t0, $s5 Exit
add $s3, $s3, 1
j Loop
Exit:

case/switch 语句

大多数程序设计语言都有 case/switch 语句，使得程序员可以根据某个变量的值选择不同的分支。
实现方式是: 将多个指令序列分支的地址编码为一张表，即转移表(jump table)
MIPS 提供了寄存器跳转指令 jr 意为 jump register，用来无条件跳转到寄存器的指定的地址。

计算机硬件对过程的支持

过程(procedure)或函数是程序员进行结构化编程的工具，两者有助于提高程序的可理解性和代码的可重用性。
MIPS 在为过程调用分配寄存器时遵循下述约定:

$a0-$a3: 用于传递参数的 4 个参数寄存器
$v0-$v1: 用于返回值的两个值寄存器
$ra: 用于返回起始点的返回地址寄存器

除了分配这些寄存器之外，MIPS 还包括一条过程调用指令: 跳转到某个地址的同时将下一条指令的地址保存在 $ra 中，这条跳转和链接指令(jump and link instruction)格式为:
jal procedureAddress
在存储程序概念中，使用一个寄存器保存当前运行的指令地址是决定必要的。这个寄存器称为程序计数器(program counter)，在 MIPS 中简称 PC。jal 指令实际将 PC+4 保存在 $ra 中。

使用更多的寄存器

换出寄存器最理想的数据结构是栈(stack): 一种后进先出的队列。
栈需要一个指针指向栈中最新分配的地址，以指示下一个过程置换出寄存器的位置。或是寄存器旧值的存放位置。在每次寄存器进行保存或恢复时，栈指针(stack pointer)以字为单位进行调整。
MIPS 为栈指针准备了第 29 号寄存器 $sp。
将数据放入栈中的操作称为 push。
从栈中移除数据的操作称为 pop。